package com.kongge.algorithm.demo;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import com.kongge.algorithm.tree.TreeNode;

/**
 * 输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径，从树的根节点开始往下一直到叶子节点所经过的结点形成一条路径。
 * 
 * @author gaoshiqi
 *
 */
public class FindBinaryTreePath implements IAlgorithm {

	public void execute() {
		TreeNode<Integer> root = TreeNode.createTree(new Integer[] {10, 5, 12, 4, 7});
		int expectedSum = 22;
		List<List<Integer>> pathList = findPath(root, expectedSum);
		if (pathList != null && pathList.size() != 0) {
			System.out.println("和为 " + expectedSum + " 的路径如下：");
			for (int i = 0; i < pathList.size(); i++) {
				System.out.print("第" + (i + 1) + "条路径为：");
				List<Integer> list = pathList.get(i);
				for (int j = 0; j < list.size(); j++) {
					System.out.print(list.get(j) + " ");
				}
				System.out.println();
			}
		}
	}
	
	private List<List<Integer>> findPath(TreeNode<Integer> root, int expectedSum) {
		if (root == null || expectedSum < root.value) {
			return null;
		}
		List<List<Integer>> pathList = new LinkedList<List<Integer>>();
		Stack<Integer> pathStack = new Stack<Integer>();
		traveceTree(root, expectedSum, pathStack, pathList);
		return pathList;
	}
	
	private void traveceTree(TreeNode<Integer> root, int expectedSum, Stack<Integer> pathStack, List<List<Integer>> pathList) {
		if (root == null || expectedSum < root.value) {
			return;
		}
		expectedSum -= root.value;
		pathStack.push(root.value);
		if (expectedSum == 0) {
			List<Integer> list = new LinkedList<Integer>();
			for (int i = 0; i < pathStack.size(); i++) {
				list.add(pathStack.get(i));
			}
			pathList.add(list);
		} else {
			traveceTree(root.left, expectedSum, pathStack, pathList);
			traveceTree(root.right, expectedSum, pathStack, pathList);
		}
		expectedSum += root.value;
		pathStack.pop();
	}
}
